package com.so;

/**
 * 第37题
 * 求两个单向链表的第一个公共节点
 *
 * @author qgl
 * @date 2017/08/15
 */
public class FindFirstCommonNode37 {

    /**
     * 链表
     */
    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 解法一：长链表先走，需要遍历链表
     * @param pHead1
     * @param pHead2
     * @return
     */
    public static ListNode findFirstCommonNode1(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        int length1 = getListNodeLength(p1);
        int length2 = getListNodeLength(p2);
        int diff = 0;
        if (length1 - length2 > 0) {
            diff = length1 - length2;
            while (diff-- > 0) {
                pHead1 = pHead1.next;
            }
        } else {
            diff = length2 - length1;
            while (diff-- > 0) {
                pHead2 = pHead2.next;
            }
        }

        while (pHead1 != null && pHead2 != null) {
            System.out.println(pHead1.val);
            System.out.println(pHead2.val);
            if (pHead1 == pHead2) {
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }

    /**
     * 获取链表长度
     * @param root
     * @return
     */
    private static int getListNodeLength(ListNode root) {
        int result = 0;
        if (root == null)
            return result;
        ListNode point = root;

        while (point != null) {
            point = point.next;
            result++;
        }
        return result;
    }

    /**
     * 解法二：不需要遍历链表
     * @param pHead1
     * @param pHead2
     * @return
     */
    public static ListNode findFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }

        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 != null ? p1.next : pHead2);
            p2 = (p2 != null ? p2.next : pHead1);
        }
        return p1;
    }

    public static ListNode findFirstCommonNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode node1 = headA;
        ListNode node2 = headB;
        while (node1 != node2) {
            node1 = (node1 == null) ? headB : node1.next;
            node2 = (node2 == null) ? headA : node2.next;
        }
        return node1;
    }

    private static void test() {
        ListNode head1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n5 = new ListNode(5);
        head1.next = n2;
        n2.next = n3;
        n3.next = n5;

        ListNode head2 = new ListNode(3);
        ListNode head21 = new ListNode(5);
        head2.next = head21;
        ListNode firstCommonNode1 = findFirstCommonNode1(head1, head2);
        System.out.println(firstCommonNode1.val);
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode second1 = new ListNode(2);
        ListNode third1 = new ListNode(3);
        ListNode forth1 = new ListNode(6);
        ListNode fifth1 = new ListNode(7);
        head1.next = second1;
        second1.next = third1;
        third1.next = forth1;
        forth1.next = fifth1;

        ListNode head2 = new ListNode(4);
        ListNode second2 = new ListNode(5);
        ListNode third2 = new ListNode(6);
        ListNode forth2 = new ListNode(7);

        head2.next = second2;
        second2.next = forth1;
        third2.next = forth2;
        ListNode firstCommonNode1 = findFirstCommonNode1(head1, head2);
        System.out.println(firstCommonNode1.val);

        test();
    }
}
